package my.test.datastructures.queue;

import java.util.LinkedList;

/**
 * @author LalitR
 */
public class PriorityQWithLLApp {
	public static void main(String[] args) {
		PriorityQWithLL thePQ = new PriorityQWithLL(5);
		thePQ.insert(30, 1);
		thePQ.insert(50, 2);
		thePQ.insert(10, 1);
		thePQ.insert(40, 3);
		thePQ.insert(20, 4);
		thePQ.insert(60, 3);
		thePQ.insert(70, 2);
		thePQ.insert(15, 5);
		thePQ.insert(11, 5);
		while (!thePQ.isEmpty()) {
			long item = thePQ.remove();
			System.out.print(item + " "); // 10, 20, 30, 40, 50
		} // end while
		System.out.println("");
	}
}

class PriorityQWithLL {
	// array in sorted order, from max at 0 to min at size-1
	private int maxSize;
	private LinkedList<Integer>[] queArray;

	// -------------------------------------------------------------
	public PriorityQWithLL(int s) // constructor
	{
		maxSize = s;
		queArray = (LinkedList<Integer>[]) new LinkedList[maxSize];
		for (int i = 0; i < maxSize; i++) {
			queArray[i] = new LinkedList<Integer>();
		}
	}

	// -------------------------------------------------------------
	public void insert(int item, int priority) // insert item
	{
		queArray[priority-1].addLast(item);
		         
	} // end insert()

	// -------------------------------------------------------------
	public int remove() // remove minimum item
	{
		return queArray[getMinPriorityIdx()].removeFirst();
	}

	// -------------------------------------------------------------
	public long peekMin() // peek at minimum item
	{
		return queArray[getMinPriorityIdx()].peekFirst();
	}

	// -------------------------------------------------------------
	public boolean isEmpty() // true if queue is empty
	{
		return (getMinPriorityIdx() == -1);
	}
	
	private int getMinPriorityIdx()
	{
		int idx = -1;
		for (int i = 0; i < maxSize; i++) {
			if (queArray[i].size() > 0) { 
				idx = i; 
				break;
			}
		}
		return idx;
	}

}
